##########################
###### MINI-MAX A-B ######
##########################
import time
import Config


#只有进行自己的搜索
global BoardSituation
BoardSituation = set()


def alpha_beta_search(node):
    infinity = float('inf')
    best_val = -infinity
    alpha = -infinity
    t = time.time()
    node.getSuccessors(BoardSituation)
    best_state = None
    for state in node.children:
        value = max_value(state, best_val, alpha)
        if value > best_val:
            best_val = value
            best_state = state

    if Config.DEBUG == True:
        print("AlphaBeta:  Utility Value of Root Node: = " + str(best_val))
        print("cost time is: " + str(time.time() - t))
        global count
        count = 1
        def countChild(node):
            global count
            count = count + len(node.children)
            for child in node.children:
                countChild(child)

        countChild(node)
        print("tree children is : " +str(count))
    return best_state.move

def max_value(node, alpha, beta):
    # print("AlphaBeta-->MAX: Visited Node")
    infinity = float('inf')
    value = -infinity

    node.getSuccessors(BoardSituation)
    if node.isTerminal:
        return node.value
    for state in node.children:
        value = max(value, max_value(state, alpha, beta))
        if value <= alpha:
            return value
        alpha = max(alpha, value)
    return value


    #                     #
    #   UTILITY METHODS   #
    #                     #
    #
    # # successor states in a game tree are the child nodes...
    # def getSuccessors(self, node):
    #     assert node is not None
    #     return node.children
    #
    # # return true if the node has NO children (successor states)
    # # return false if the node has children (successor states)
    # def isTerminal(self, node):
    #     assert node is not None
    #     return len(node.children) == 0
    #
    # def getUtility(self, node):
    #     assert node is not None

